package com.lxl.sort;

/**
 * @Author lixilin
 * @Date 2021/12/26 16:34
 * @Description
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {42, 12, 2, 3, 6, 25, 12, 28};
        mSort(arr);
        for (int i : arr) {
            System.out.println(" " + i);
        }

    }

    public static void mSort(int[] arr) {
        if (arr == null || arr.length ==0) {
            return;
        }
        int[] temp = new int[arr.length];
        mSort(arr,0,arr.length-1,temp);
    }
    public static void mSort(int[] arr,int left,int right,int[] temp) {
        if (left < right) {
            // 中间索引
            int mid = (left+right)/2;
            // 左递归
            mSort(arr,left,mid,temp);
            // 右递归
            mSort(arr,mid+1,right,temp);
            // 合并
            merge(arr, left, mid, right, temp);
        }

    }

    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int l =left;// 左边有序数组的起始索引位置
        int r = mid+1;// 右边有序数组的起始索引位置
        int t =0;// 临时数组的索引位置

        //一, 把左右两边有序数组的元素按照规则填充到temp数组
        while (l <= mid && r <= right) {
            if (arr[l] <= arr[r]) {
                temp[t++] = arr[l++];
            } else {
                temp[t++] = arr[r++];
            }
        }
        // 二, 将有剩余数据的左或右边的有序数组的剩余部分填充到temp数组
        while (l <= mid) {
            temp[t++] = arr[l++];
        }
        while (r <= right) {
            temp[t++] = arr[r++];
        }
        // 三, 将temp数组的元素拷贝到arr中,注意: 并不是每次都拷贝所有
        t =0;
        int tempLeft = left;
        while (tempLeft <= right) {
            arr[tempLeft++] = temp[t++];
        }

    }
}
